// 此文件仅用于实现归并排序中的合并两个有序序列片段的函数
#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int> nums,vector<int>& source_nums,int left,int mid,int right){
    // vector 数组要想引用的话,得明确加上&;
    /**
     * 合并两个有序序列片段(两个序列分别是[left,mid],(mid,right]),将结果放到source_nums对应位置;注意这里的位置都是下标从 1 开始的,因此索引数组时要减一;
     * @param nums 待并入source_nums的数组
     * @param source_nums 原始数组
     * @param left 第一个序列的最左位置;
     * @param mid 中间位置;两个有序片段的分界点
     * @param right 第二个序列的最右位置
     * @return 无返回值
     */
    int j,k;
    for (j = mid + 1, k = left; left <= mid && j <= right; k++)
    // j 用于遍历第二个有序的序列;用 left 遍历第一个有序序列;k 用于指向待存放的source_nums的位置
    {
        if (nums[left - 1] < nums[j - 1]) // 注意这里需要减一才是数组的下标
        {
            source_nums[k-1] = nums[left - 1];
            left++;
        }
        else
        {
            source_nums[k-1] = nums[j - 1];
            j++;
        }
    }
    if (left <= mid)
    {
        // 第一个序列还没有遍历完
        for (; left <= mid; left++)
        {
            source_nums[k - 1] = nums[left - 1];
            k++;
        }
    }
    if (j <= right)
    {
        // 第二个序列还没有遍历完
        for (; j <= right; j++)
        {
            source_nums[k - 1] = nums[j - 1];
            k++;
        }
    }
}

int main(){
    vector<int> nums={10,30,50,70,90,20,40,60,80}; // 需要并入TR1的数组;nums前半部分和后半部分分别有序
    vector<int> source_nums={50,10,90,30,70,40,80,60,20}; // 待并入到的原始数组
    int left=1;
    int right=nums.size();
    int mid=(left+right)/2;
    Merge(nums,source_nums,left,mid,right);
    for (int i = 0; i < source_nums.size(); i++)
    {
        cout<<source_nums[i]<<",";
    }
    cout<<endl;
    return 0;
}